package nc.jv.Sort;

@Deprecated
public class MergeSort
{

        /**
         * Способ набора данных для сортировки
         * 
         * <ul>
         * <li>{@code BEST} Наилучший случай
         * <li>{@code NORMAL} Среднестатистический набор
         * <li>{@code WORST} Худший случай
         * </ul>
         */
        enum Case {WORST, NORMAL, BEST};
        
        @SuppressWarnings("rawtypes")
        public static void main(String[] args)
        {
                final int LENGTH = 8;
                
                Comparable[] array = generateArray(LENGTH, Case.NORMAL);
                print(array);
                
                long startTime = System.currentTimeMillis();
                sort(array);            
                System.out.printf("Elapsed time: %d ms\n", (System.currentTimeMillis() - startTime));
                
                print(array);
        }
        
        /**
         * Сортирует передаваемый массив {@code array}
         * @param array
         *                Сортируемый массив. Элементы массива должны реализовывать интерфейс {@link Comparable}
         */
        @SuppressWarnings("rawtypes")
        public static void sort(Comparable[] array)
        {
                Comparable[] sa = array; // sorted array
                array = array.clone();   // unsorted/temporary array            
                
                int pow2length = minPowOfTwo(array.length);

                Comparable[][] c = new Comparable[][] {array, sa};
                if (log2(pow2length) % 2 == 0) // if length == 4, 16, 64 etc.
                        xchg(c);
                
                for (int p = 1; 2*p <= pow2length; p *= 2) // while p less than half
                {
                        for (int i = 0; i < array.length; i += 2*p)
                                merge(c[0], c[1], i, p);
                        xchg(c);
                }
        }
        
        /**
         * Вспомогательный метод для сортировки массива
         * 
         * <p> В массиве {@code unsortedArray} выделяется блок с позиции {@code startIndex} размером {@code p}.
         * За ним выделяется второй блок размером {@code p}. Оба блока сливаются попеременным шаганием по блокам
         * в массив {@code sortedArray} начиная с позиции {@code startIndex}. Когда один из блоков заканчивается,
         * все оставшиеся элементы второго блока добавляются в резельтирующий массив {@code sortedArray}
         * 
         * @param unsortedArray
         *                Массив, который нужно отсортировать
         * 
         * @param sortedArray
         *                Массив, в который будет передан отсортированный массив {@code unsortedArray}
         * 
         * @param startIndex
         *                Начало блока для сортировки
         * 
         * @param p
         *                Размер блока сортировки
         */
        @SuppressWarnings({ "rawtypes", "unchecked" })
        private static void merge(Comparable[] unsortedArray,
                                                          Comparable[] sortedArray,
                                                          final int startIndex,
                                                          int p)
        {
                int leftIndex  = startIndex,
                        rightIndex = startIndex + p,
                        outIndex   = startIndex;
                final int leftEnd  = (startIndex + p) <= unsortedArray.length
                                                         ? startIndex + p
                                                         : unsortedArray.length,
                                  rightEnd = (startIndex + 2*p) <= unsortedArray.length
                                                         ? startIndex + 2*p 
                                                         : unsortedArray.length;

                while (leftIndex < leftEnd && rightIndex < rightEnd)
                        if (unsortedArray[leftIndex].compareTo(unsortedArray[rightIndex]) < 0) // sort by ascending
                                sortedArray[outIndex++] = unsortedArray[leftIndex++];
                        else
                                sortedArray[outIndex++] = unsortedArray[rightIndex++];
                
                while (leftIndex < leftEnd)
                        sortedArray[outIndex++] = unsortedArray[leftIndex++];
                
                while (rightIndex < rightEnd)
                        sortedArray[outIndex++] = unsortedArray[rightIndex++];                  
        }
        
        /**
         * Меняет местами первые два элемента в массиве
         * 
         * <p> Необходимо для {@link #sort(Comparable[])}
         * 
         * @param array
         *                Любой массив объектного типа
         */
        private static void xchg(Object[] array)
        {
                Object temp = array[0];
                array[0] = array[1];
                array[1] = temp;
        }
        
        /**
         * Генерирует входные данные для сортировки слиянием
         * 
         * @param length
         *                Длина генерируемого массива
         * 
         * @param c
         *                Способ генерирование массива. <i>См.</i> {@link Case}
         *                <ul><li>Лучший случай - массив отсортирован
         *                        <li>Среднестатистический случай - случайный набор данных
         *                        <li>Худший случай - массив вообще не отсортирован</ul>
         * 
         * @return Массив заданной длины {@code length} сгенерированный способом {@code c}  
         */
        @SuppressWarnings("rawtypes")
        public static Comparable[] generateArray(int length, Case c)
        {
                Comparable[] array = new Integer[length];
                
                if (c == Case.BEST)
                        for (int i = 0; i < length; i++)
                                array[i] = i;
                else if (c == Case.NORMAL)
                        for (int i = 0; i < length; i++)
                                array[i] = (int) (Math.random()*100);
                else if (c == Case.WORST)
                        for (int i = 0; i < length; i++)
                                array[i] = length - i;
                else
                        array =  null;
                
                return array;
        }
        
        /**
         * Определяет минимальную степень числа 2, большую заданного
         * 
         * <p>
         * <code> minPowOfTwo(4) </code> вернет 4
         * <p>
         * <code> minPowOfTwo(5) </code> вернет 8
         * 
         * @param number
         *                Заданное число
         * 
         * @return Степень числа 2, большую заданного числа {@code number}
         */
        private static int minPowOfTwo(int number)
        {
                return isPowerOfTwo(number)
                           ? number                                                       // 4 -> 4
                           : 2*Integer.highestOneBit(number); // 5 -> 8
        }
        
        /**
         * Определяет является ли число степенью 2
         * 
         * @param number
         *                Число
         * 
         * @return
         *                 <ul><li>{@code true} если число является степенью 2
         *                         <li>{@code false} если число не является степенью 2</ul>
         */
        private static boolean isPowerOfTwo(int number) 
        {
                return (number & -number) == number;
        }
        
        /**
         * Определяет логарифм числа по основанию 2
         * 
         * @param number
         *                Число, логарифм которого нужно найти
         * 
         * @return
         *                 Логарифм числа {@code number} по основанию 2
         */
        private static int log2(int number)
        {
                return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(number);
        }
        
        /**
         * Выводит массив на экран
         * 
         * <pre>Comparable[] c = new Integer[] {1, 2, 3};
         * print(c)</pre>
         * выведет
         * <pre>1  2  3  </pre>
         * 
         * @param array
         *                Массив, который нужно вывести на экран. Элементы массива должны реализовывать интерфейс {@link Comparable} 
         */
        @SuppressWarnings("rawtypes")
        private static void print(Comparable[] array)
        {
                for (Comparable a : array)                      
                        System.out.print(a + "  ");
                System.out.println();
        }
        
}